/**
 * Project Name:trustsql_sdk File Name:Base58.java Package Name:com.tencent.trustsql.sdk.util Date:Jul 26, 20172:48:58
 * PM Copyright (c) 2017, Tencent All Rights Reserved.
 */
package com.mindata.blockchain.common.algorithm;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * Base58 is a way to encode Bitcoin addresses (or arbitrary data) as alphanumeric strings.
 * <p>
 * Note that this is not the same base58 as used by Flickr, which you may find referenced around the Internet.
 * <p>
 * You may want to consider working with {@link VersionedChecksummedBytes} instead, which adds support for testing the
 * prefix and suffix bytes commonly found in addresses.
 * <p>
 * Satoshi explains: why base-58 instead of standard base-64 encoding?
 * <ul>
 * <li>Don't want 0OIl characters that look the same in some fonts and could be used to create visually identical
 * looking account numbers.</li>
 * <li>A string with non-alphanumeric characters is not as easily accepted as an account number.</li>
 * <li>E-mail usually won't line-break if there's no punctuation to break at.</li>
 * <li>Doubleclicking selects the whole number as one word if it's all alphanumeric.</li>
 * </ul>
 * <p>
 * However, note that the encoding/decoding runs in O(n&sup2;) time, so it is not useful for large data.
 * <p>
 * The basic idea of the encoding is to treat the data bytes as a large number represented using base-256 digits,
 * convert the number to be represented using base-58 digits, preserve the exact number of leading zeros (which are
 * otherwise lost during the mathematical operations on the numbers), and finally represent the resulting base-58 digits
 * as alphanumeric ASCII characters.
 */
public class Base58Algorithm {
	public static final char[] ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();
	private static final char ENCODED_ZERO = Base58Algorithm.ALPHABET[0];
	private static final int[] INDEXES = new int[128];
	static {
		Arrays.fill(Base58Algorithm.INDEXES, -1);
		for (int i = 0; i < Base58Algorithm.ALPHABET.length; i++) {
			Base58Algorithm.INDEXES[Base58Algorithm.ALPHABET[i]] = i;
		}
	}

	/**
	 * Encodes the given bytes as a base58 string (no checksum is appended).
	 *
	 * @param input
	 *            the bytes to encode
	 * @return the base58-encoded string
	 */
	public static String encode(byte[] input) {
		if (input.length == 0) {
			return "";
		}
		// Count leading zeros.
		int zeros = 0;
		while (zeros < input.length && input[zeros] == 0) {
			++zeros;
		}
		// Convert base-256 digits to base-58 digits (plus conversion to ASCII
		// characters)
		input = Arrays.copyOf(input, input.length); // since we modify it
													// in-place
		final char[] encoded = new char[input.length * 2]; // upper bound
		int outputStart = encoded.length;
		for (int inputStart = zeros; inputStart < input.length;) {
			encoded[--outputStart] = Base58Algorithm.ALPHABET[Base58Algorithm.divmod(input, inputStart, 256, 58)];
			if (input[inputStart] == 0) {
				++inputStart; // optimization - skip leading zeros
			}
		}
		// Preserve exactly as many leading encoded zeros in output as there
		// were leading zeros in input.
		while (outputStart < encoded.length && encoded[outputStart] == Base58Algorithm.ENCODED_ZERO) {
			++outputStart;
		}
		while (--zeros >= 0) {
			encoded[--outputStart] = Base58Algorithm.ENCODED_ZERO;
		}
		// Return encoded string (including encoded leading zeros).
		return new String(encoded, outputStart, encoded.length - outputStart);
	}

	/**
	 * Decodes the given base58 string into the original data bytes.
	 *
	 * @param input
	 *            the base58-encoded string to decode
	 * @return the decoded data bytes
	 * @throws AddressFormatException
	 *             if the given string is not a valid base58 string
	 */
	public static byte[] decode(final String input) throws RuntimeException {
		if (input.length() == 0) {
			return new byte[0];
		}
		// Convert the base58-encoded ASCII chars to a base58 byte sequence
		// (base58 digits).
		final byte[] input58 = new byte[input.length()];
		for (int i = 0; i < input.length(); ++i) {
			final char c = input.charAt(i);
			final int digit = c < 128 ? Base58Algorithm.INDEXES[c] : -1;
			if (digit < 0) {
				throw new RuntimeException("Illegal character " + c + " at position " + i);
			}
			input58[i] = (byte) digit;
		}
		// Count leading zeros.
		int zeros = 0;
		while (zeros < input58.length && input58[zeros] == 0) {
			++zeros;
		}
		// Convert base-58 digits to base-256 digits.
		final byte[] decoded = new byte[input.length()];
		int outputStart = decoded.length;
		for (int inputStart = zeros; inputStart < input58.length;) {
			decoded[--outputStart] = Base58Algorithm.divmod(input58, inputStart, 58, 256);
			if (input58[inputStart] == 0) {
				++inputStart; // optimization - skip leading zeros
			}
		}
		// Ignore extra leading zeroes that were added during the calculation.
		while (outputStart < decoded.length && decoded[outputStart] == 0) {
			++outputStart;
		}
		// Return decoded data (including original number of leading zeros).
		return Arrays.copyOfRange(decoded, outputStart - zeros, decoded.length);
	}

	public static BigInteger decodeToBigInteger(final String input) throws RuntimeException {
		return new BigInteger(1, Base58Algorithm.decode(input));
	}

	/**
	 * Decodes the given base58 string into the original data bytes, using the checksum in the last 4 bytes of the
	 * decoded data to verify that the rest are correct. The checksum is removed from the returned data.
	 *
	 * @param input
	 *            the base58-encoded string to decode (which should include the checksum)
	 * @throws AddressFormatException
	 *             if the input is not base 58 or the checksum does not validate. public static byte[]
	 *             decodeChecked(String input) throws AddressFormatException { byte[] decoded = decode(input); if
	 *             (decoded.length < 4) throw new AddressFormatException("Input too short"); byte[] data =
	 *             Arrays.copyOfRange(decoded, 0, decoded.length - 4); byte[] checksum = Arrays.copyOfRange(decoded,
	 *             decoded.length - 4, decoded.length); byte[] actualChecksum =
	 *             Arrays.copyOfRange(Sha256Hash.hashTwice(data), 0, 4); if (!Arrays.equals(checksum, actualChecksum))
	 *             throw new AddressFormatException("Checksum does not validate"); return data; }
	 */

	/**
	 * Divides a number, represented as an array of bytes each containing a single digit in the specified base, by the
	 * given divisor. The given number is modified in-place to contain the quotient, and the return value is the
	 * remainder.
	 *
	 * @param number
	 *            the number to divide
	 * @param firstDigit
	 *            the index within the array of the first non-zero digit (this is used for optimization by skipping the
	 *            leading zeros)
	 * @param base
	 *            the base in which the number's digits are represented (up to 256)
	 * @param divisor
	 *            the number to divide by (up to 256)
	 * @return the remainder of the division operation
	 */
	private static byte divmod(final byte[] number, final int firstDigit, final int base, final int divisor) {
		// this is just long division which accounts for the base of the input
		// digits
		int remainder = 0;
		for (int i = firstDigit; i < number.length; i++) {
			final int digit = number[i] & 0xFF;
			final int temp = remainder * base + digit;
			number[i] = (byte) (temp / divisor);
			remainder = temp % divisor;
		}
		return (byte) remainder;
	}

}
